The present invention relates generally to computer graphics displays, and particularly to the display of straight line segments on computer graphics displays.
Computer graphics systems are commonly used to display graphical representations of two-dimensional or three-dimensional objects on a two-dimensional display screen. The display screen is typically a cathode ray tube (CRT) device and is divided into arrays of elements referred to as pixels which can be stimulated to emit a range of visual light. The stimulation of the pixels is performed sequentially in some regular order and is repeated typically 50 to 80 times a second in order to maintain a screen image whose intensity does not noticeably change with time.
Typical CRT devices for use with graphics workstations are xe2x80x9craster scanxe2x80x9d display devices. Modem raster scan display devices generate images comprising a multiplicity of parallel, non-overlapping bands of pixels comprising sets of parallel lines.
In typical computer graphics systems, an object to be represented on the display screen is broken down into a plurality of graphics primitives. Primitives are the basic components of a graphics picture and may include points, lines, vectors, and polygons, such as triangles. Typically, a hardware/software scheme is implemented to render, or draw, on the two-dimensional display screen, the graphics primitives that represent a particular view of one or more objects being represented on the screen.
As display systems have increased in complexity to meet an ever-increasing demand for a larger display area and a greater fidelity in the representation of objects on the display screen, the load on the hardware and software required to process the image has also increased. An increase in object representation fidelity has been accomplished, in part, by a decrease in pixel size with a corresponding increase in the number of pixels. The total number of pixels required has also increased as the size of the screen used for display has increased.
To improve performance with the increasing demands upon the rendering system, designers are employing varying techniques to add parallelism in the rendering process. One such technique divides the display""s screen space into multiple regions. If a primitive or any portion of a primitive lies within a region, then that region is selected for further processing by a rasterizer that will ultimately render the image contained in that region. Parallelism can now be obtained by having multiple rasterizers available which can be independently assigned to the screen regions that have objects to be rendered, thus allowing multiple objects to be simultaneously rendered.
Typical systems render a straight line segment via a stepping algorithm. A starting point on the display for the line is determined with the pixel corresponding to that point being illuminated. The next pixel to be illuminated is determined by stepping along the major axis one pixel position and then computing the value of the pixel in the minor axis direction. The major axis is defined as that axis to which the line to be rendered forms an included angle of less than or equal to 45 degrees. The minor axis then is the other axis of a Cartesian coordinate system. For example, if the line to be rendered forms an included angle of 37 degrees to the x-axis, then the x-axis is considered to be the major axis and the y-axis the minor axis. In like manner, the next pixel to be illuminated is determined by again stepping one pixel position along the major axis, which is the x-axis in the example, and then computing the corresponding minor axis position, the y-axis in the example, of the pixel on the line to be rendered. This process is repeated until the end of the line is reached. In a region-based rasterizer system, what is desired is a technique that focuses only on the portion of the line within the region currently being processed rather than a traditional technique of starting at the beginning of the line segment and processing to the end, crossing potentially many different regions.
As noted earlier, previous methods for rendering straight line segments have typically used a single rasterizer to generate all the pixels for a given line from the start of the line to the end of the line without regard to regions or region boundaries. With region-based rasterization however, it is possible that a single line might have several rasterizers generating pixels for that line, each operating within its assigned screen region. By identifying which regions the line passes thru, only rasterizers assigned to those regions need to be activated to process the line, freeing rasterizers assigned to the other regions to process primitives appearing in their regions. Techniques disclosed herein limit the area of the screen that must be considered in drawing the straight line segment providing for more computationally-efficient techniques. In the following detailed description and in the several figures of the drawings, like elements are identified with like reference numerals.
In one embodiment of the invention, a method for selecting auxiliary screen regions to activate in rendering a straight line segment on a screen of a computer monitor, wherein the straight line segment comprises points defined by an algebraic expression equal to zero, wherein the expression is expressed as a first constant multiplied by a x-axis value plus a second constant multiplied by a y-axis value plus a third constant, wherein the straight line segment has a width is disclosed. The method includes the steps of overlaying a rectangular grid to associated screen region boundaries, wherein the screen comprises a screen space divided into multiple screen regions, shifting the rectangular grid in a preselected direction parallel to a preselected axis by a fraction of the width of the straight line segment, and for each corner point of the shifted rectangular grid, computing the expression, obtaining an algebraic sign of the result of computing the expression, and when the algebraic sign just obtained differs from that obtained for the expression for any other shifted rectangular grid corner point, marking the associated screen region as selected.